The FFT/DFT is widely applied to a communication system for processing a signal, including the communication system such as Long Term Evolution (LTE) involving in Orthogonal Frequency Division Multiplexing (OFDM), Worldwide Interoperability for Microwave Access (Wimax), China Mobile Multimedia Broadcasting (CMMB), Digital Video Broadcasting (DVB), Digital Audio Broadcast (DAB), Digital Subscriber Line (DSL) or the like.
For DFT, the DFT of finite length sequence x(n) with a length of N is computed by the following formula:
      X    ⁡          (      k      )        =            DFT      ⁡              [                  x          ⁡                      (            n            )                          ]              =                  ∑                  n          =          0                          N          -          1                    ⁢                        x          ⁡                      (            n            )                          ⁢                                            W              N              nk                        ⁡                          (                                                k                  =                  0                                ,                1                ,                                                      …                    ⁢                                                                                  ⁢                    N                                    -                  1                                            )                                .                    In general, x(n) is a sequence of complex number. For a k value, it is needed N complex multiplications and (N−1) complex additions to compute a x(k) value according to the above formula, so the amount for computing directly the DFT is positive proportional to the square of the length N of a transform interval. When N is large, too large amount of computation will result in too long computation time and will result in waste of software and hardware resources. Therefore, the FFT emerges in order to avoid the problem of big difficulty when the signal is processed in real time by using the DFT directly.
The FFT is a fast algorithm of the DFT, which may simplify the amount of computation of the DFT, and improves the operation speed. Since the coefficient
      W    N    nk    =      ⅇ                  -        j            ⁢                          ⁢                        2          ⁢          π                N            ⁢      nk      is a periodic function and is of periodicity and symmetry. According to the symmetry of WNnk, it is obtained that (WNnk)*=WN−nk, WNk+n/2=−WNk, WNn(N+k)=WNk(N+n)=WNnk and WNn(N−k)=WNk(N−n)=WN−nk. The operation of the DFT may be broken up into DFT operations of fewer points to the greatest extent by taking advantage of the periodicity and symmetry of WNnk.
At present, a traditional FFT/DFT may be computed by using a general-purpose operation unit or a special-purpose butterfly operation unit of some form. The traditional general-purpose operation unit may implement a real multiply operation, a real add operation, a real multiply-add operation, a real multiply-accumulate operation, a complex multiply operation, a complex add operation, a complex multiply-add operation, a complex multiply-accumulate operation and a radix 2 butterfly operation, but may not implement N-point high-order butterfly operation (N is a positive integer greater than 2). When the N-point high-order butterfly operation is performed, a relatively complicated special-purpose butterfly operation unit is usually adopted, for example the special-purpose butterfly operation unit which supports radix 3, radix 4 and radix 5 butterfly operations simultaneously may be adopted. However, the special-purpose butterfly operation unit of this type can only process the FFTs/DFTs of some fixed points after the special-purpose butterfly operation unit is designed. In a concrete application environment, the FFTs/DFTs of multiple fixed points may need to be computed. The special-purpose butterfly operation unit in the related art exits the problem of low flexibility, and at the same time, the special-purpose butterfly operation unit of this type often needs to consume more hardware resources and exits the problem of high complexity and power consumption. Thus, the operation speed is low when the signal is processed in real time, which is not conducive to the application of a mobile terminal.